'''
https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/description/
'''
from collections import deque
from typing import List


class Solution:

    '''
        整体能做多少个任务，进行二分；单调性，如果能做m个任务,一定能做(l~m)个任务, 取右侧看
        key function: 能否完成 n_task个认为
            用做大能力的n_task个工人们，完成最简单的n_task任务们

            能做做，不能做吃药做，吃了药，不要浪费，做最值得的
            如果药不够了，或者吃了药还完不成，就宣布完不成
    '''
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        m, n = len(workers), len(tasks)
        tasks.sort()
        workers.sort()

        def can_finish(n_task):
            # 是否可以完成 n_task个任务
            # 选能力最大的 n_task工人， 和最简单的n_task个任务
            mono_q = deque()  # 单调队列，从左往右从小到大
            i, j = m - n_task, 0  # 工人&任务的下标, 去见分别为[m - n_task, m-1], [0, n_task - 1]
            cur_pill = 0  # 当前吃了多少药
            while i < m:
                # 解锁任务
                while j < n_task and workers[i] >= tasks[j]:
                    mono_q.append(tasks[j])
                    j += 1
                # 看我能否做任务,我是最小能力者，做最小任务
                if mono_q and workers[i] >= mono_q[0]:
                    # 能做就做
                    mono_q.popleft()
                else:
                    # 该考虑吃药了，吃了药，解锁任务，做最大的任务。因为后续工人的能力可能没我吃了药大。所以我要挑最大的任务
                    cur_ability = workers[i] + strength
                    cur_pill += 1
                    if cur_pill > pills:
                        return False
                    while j < n_task and cur_ability >= tasks[j]:
                        mono_q.append(tasks[j])
                        j += 1
                    # 能做就做
                    # print(n_task, i, j)
                    if not mono_q:  # 如果吃了药还做不了，就废了
                        return False
                    mono_q.pop()

                i += 1
            return True

        l, r = 0, min(m, n)
        ans = 0
        while l <= r:
            n_task = (l + r) // 2
            if can_finish(n_task):
                ans = n_task
                l = n_task + 1
            else:
                r = n_task - 1
        return ans


tasks = [10,15,30]
workers = [0,10,10,10,10]
pills = 3
strength = 10
print(Solution().maxTaskAssign(tasks, workers, pills, strength))